//
// Created by Tan Ke on 2024/1/5.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

/*
 * 使用recordMap[i][j]来保存 从arrayA[i] * arrayA[i+1] * ... * arrayA[j]的值
 */

struct Item {
    int val;
    bool flag;
};

int calcFunc(int* arrayA, int arrayASize, struct Item** recordMap, int i, int j)
{
    //printf("enter: %d:%d\n", i, j);
    if (recordMap[i][j-i].flag == true) {
        //printf("shou return: %d:%d\n", i, j);
        return recordMap[i][j-i].val;
    }
    recordMap[i][j-i].val = arrayA[i] * calcFunc(arrayA, arrayASize, recordMap, i + 1, j);
    recordMap[i][j-i].flag = true;

    //printf("leave: %d:%d\n", i, j);
    return recordMap[i][j-i].val;
}

int* statisticalResult(int* arrayA, int arrayASize, int* returnSize)
{
    struct Item** recordMap = (struct Item**)malloc(sizeof(struct Item*) * arrayASize);
    for (int i = 0; i < arrayASize; i ++) {
        struct Item* row = (struct Item*)malloc(sizeof(struct Item) * (arrayASize - i));
        for (int m = 0; m < (arrayASize - i); m ++) {
            row[m].val = 0;
            row[m].flag = false;
        }
        recordMap[i] = row;
    }

    /* 初始化边界值 */
    for (int i = 0; i < arrayASize; i ++) {
        recordMap[i][0].val = arrayA[i];
        recordMap[i][0].flag = true;
    }

    int *result = (int*)malloc(sizeof(int) * arrayASize);

    if (arrayASize == 1) {
        result[0] = 0;
        *returnSize = 1;
        return result;
    }

    if (arrayASize == 2) {
        result[0] = arrayA[1];
        result[1] = arrayA[0];
        *returnSize = 2;
        return result;
    }

    for (int i = 0; i < arrayASize; i ++) {
        if (i == 0) {
            result[i] = calcFunc(arrayA, arrayASize, recordMap, 1, arrayASize - 1);
        } else if (i == arrayASize - 1) {
            result[i] = calcFunc(arrayA, arrayASize, recordMap, 0, arrayASize - 2);
        } else {
            result[i] = calcFunc(arrayA, arrayASize, recordMap, 0, i - 1) * calcFunc(arrayA, arrayASize, recordMap, i + 1, arrayASize - 1);
        }
    }

    *returnSize = arrayASize;
    return result;
}

int main(void)
{
#if 0
    int array1[5] = {2, 4, 6, 8, 10};
    int result1Size = 0;
    int* result1 = statisticalResult(array1, 5, &result1Size);

    for (int i = 0; i < result1Size; i ++) {
        printf("%d ", result1[i]);
    }
    printf("\n");

    int array2[2] = {1, -2};
    int resultSize2 = 0;
    int* result2 = statisticalResult(array2, 2, &resultSize2);

    for (int i = 0; i < resultSize2; i ++) {
        printf("%d ", result2[i]);
    }
    printf("\n");
#endif

    int array3[17] = {-7, -1, 1, 4, -2, -2, -2, -9, -5, 3, -7, -6, 2, -6, -8, -4, 3};
    int resultSize3 = 0;
    int *result3 = statisticalResult(array3, 17, &resultSize3);

    for (int i = 0; i < resultSize3; i ++) {
        printf("%d ", result3[i]);
    }
    printf("\n");

    return 0;
}